The present invention relates generally to data encoding and in particular to error correcting code encoder and decoders.
The transmission of data through a noisy channel could introduce errors into the data stream. In order to reduce the amount of errors in the transmitted sequence and to avoid retransmissions coding techniques have been developed that provide the ability to detect and correct errors in a sequence. This is achieved usually through the addition of redundant information as part of the transmission. Here the term transmission is used broadly to include transfer of data through different types of medium. This can include communication mediums such as those used in wired, wireless, satellite, and other technologies. This can also include storage mediums such as magnetic, semiconductor, and other types of memory.
Some of the most popular and powerful coding techniques use Forward Error Correcting Codes (FECC) that operate on blocks of data rather than streams of data, such as Parallel Concatenated Convolutional Codes (PCCC or Turbo), Serially Concatenated Convolutional Codes (SCCC) Low Density Parity Check Codes (LDPCC), Turbo Product Codes (TPC) and other Turbo-Like Codes (TLC). Although all these codes differ significantly in terms of the code structure, they share some common features. First, they all operate on the data on a block basis, meaning that the data is not encoded in a continuous stream, but rather partitioned in blocks of a predetermined size. Second, all these codes use iterative decoding methods, therefore they generally require that a block of data is stored in memory and accessed several times before the results of the encoding and decoding processes become available. Finally it is well known that all these codes can achieve better performance against noise, but also better data rates as the data block size increases.
Therefore, there are many benefits associated with larger block sizes and it would be beneficial to be able to use as large of a block size as possible in all these cases. One obvious problem however that is related to all these coding structures is memory usage. Generally speaking, the memory usage directly translates to physical memory area on a chip (field programmable gate array (FPGA), application-specific integrated circuit (ASIC) or custom very-large-scale integration (VLSI) chip) that implements such a code and therefore higher implementation cost. With even small block sizes, it is often the case that the size of the processing logic in the implementation is comparable or even sometimes several times smaller than the size of the memory required for storing the data.
Designers are hence forced to trade between performance and memory area in order to achieve an implementation that can satisfy their requirements using less memory area. The purpose of this invention is to show that there exist special area-efficient memory types that are ideally suited for use in such coding structures so that the memory area cost associated with a given implementation is significantly smaller than the one required when using commonly used memory structures.
FIG. 1 is block diagram of a prior art parallel concatenated convolutional code (PCCC) FECC 100. PCCC 100 receives a single input signal and outputs two encoded output signals that each includes an encoded version of the input signal. To produce the first output signal, the input signal is convolutionally encoded prior to output. To produce the second output signal, the input signal is first interleaved and then convolutionally encoded prior to output.
PCCC 100 includes an interleaver 110, a first convolution code module (CC) 120, and a second convolution code module (CC) 130. PCCC 100 receives an input signal to be encoded, and the input signal is passed to interleaver 110 and to CC 120. CC 120 convolutionally encodes the input signal and outputs a first encoded output signal. Interleaver 110 interleaves the input signal and outputs the interleaved signal. CC 130 receives the interleaved signal as an input and convolutionally encodes the interleaved signal. CC 130 then outputs the encoded signal as the second encoded output signal.
Interleaving and convolutional encoding are two means of error correction that are well known in the art. Data interleaving may be used to protect against burst errors in a transmission that may overwrite a number of bits in a transmission. Data to be transmitted is often broken up into a plurality of control words and each of these control words may be self-correcting up to a certain number of bits. For example, an n-bit control word may be 1-bit self-correcting, meaning that if 1 bit of the n bits comprising the control word is overwritten or lost in transmission, the error can be detected and corrected. However, if an error comprising 2 or more bits occurs, the error cannot be self-corrected, and depending upon the decoding algorithm being applied the code word may either fail to be decoded or a the false positive may result where the decoding algorithm misidentifies the code word as a different code word due to the error.
The control words may then be interleaved to further protect against burst errors. For example, the i-th bit of each n-bit control words may be transmitted, then the i+1th bit of each n-bit control word may be transmitted, and so on until each bit of a group of the first n code words has been transmitted. Thus, if a burst error occurs, the number of bits lost from any one code word is likely to be minimized.
Convolutional coding is another type of self-correcting code. Convolutional encoding transforms an m-bit control word into an n-bit symbol (where n>m) and the transformation is a function of the last k information symbols with k being the constraint length of the code.
One skilled in the art will recognize that the methods for interleaving data and for convolutional encoding of data described herein are merely exemplary and that other methods for interleaving and convolutional encoding might also be used in alternative implementations.
FIG. 2 is a block diagram of a prior art serially concatenated convolutional code (SCCC) FECC 200. Like the PCCC described above, a SCCC includes two convolutional encoder modules and an interleaver, but instead of producing two separate encoded output signals, the input signal is serially encoded by both convolutional encoder modules.
SCCC 200 includes a first convolution coder module (CC) 210, an interleaver 220, and a second convolution coder (CC) module 230. CC 210 receives an input signal to be encoded and performs a first convolutional coding step on the data. CC 210 outputs the encoded data, and interleaver 220 receives the encoded data as an input. Interleaver 220 interleaves the data and outputs the interleaved data. CC 230 receives the interleaved data and performs a second convolutional coding step on the data. CC 230 then outputs the encoded data.
FIG. 3 is a block diagram of a prior art hybrid concatenated convolutional code (Hybrid CCC) FECC 300. Like PCCC 100 described above, hybrid CCC 300 produces two output data signals. The first output data signal is identical to the input signal, and the second output data signal is identical to that which is produced by SCCC 200 described above.
Hybrid CCC 300 includes a first convolutional code module (CC) 310, an interleaver 320, and a second convolutional code module (CC) 330. Hybrid CCC 310 produces a first output signal that is identical to the input signal. CC 310 also receives the input signal as an input. CC 310 performs a first convolutional encoding step on the input signal and outputs the encoded data. Interleaver 320 receives the encoded data as an input. Interleaver 320 interleaves the encoded data and outputs the interleaved data. CC 330 receives the interleaved data as an input and performs a second convolutional encoding step on the data. CC 330 then outputs the encoded data.
Typical FPGA and ASIC implementations of Forward Error Correcting Codes (FECC) use static RAM (SRAM). In most cases, especially in high performance/throughput implementation, most RAM blocks are dual-port, meaning they can be read from or written to by two sources simultaneously. RAM blocks are also typically fairly narrow in terms of bitwidth and deep if the block size is large. The size of the address decoders is fairly large and introduces a fairly large overhead to the entire memory area required for implementation.
FECC encoders and/or decoders may be integrated into numerous portable electronic devices such as laptop computers, mobile phones, and/or other portable devices that include electronic communications capabilities. The form factor of receiver and transmitter components may be directly impacted by components such as FECC encoders and/or decoders such as those described above. Electronics designers and manufacturers attempt to minimize the footprint of the individual components of the devices that they are designing and producing in order to minimize the manufacturing costs as well as minimize the form factor of the electronic device.
Accordingly, a solution that advantageously addresses the performance and implementations problems presented in conventional FECCs is desired.